package com.leetcode.union_find;

/**
 * @author Dennis Li
 * @date 2020/7/28 21:52
 */
public class MakeConnected_1319 {

    private int[] computers;

    public int makeConnected(int n, int[][] connections) {
        if (connections.length < n - 1) return -1;
        computers = new int[n];
        for (int i = 0; i < n; i++) {
            computers[i] = i;
        }
        for (int[] conn : connections) {
            union(conn[0], conn[1]);
        }
        int count = 0;
        for (int i = 0; i < n; i++) {
            // 只要有电脑不连通，则需要增加一个连通块
            if(computers[i] == i) count++;
        }
        // 实际操作数再减1才是答案
        return count - 1;
    }

    private int find(int x) {
        return computers[x] == x ? x : (computers[x] = find(computers[x]));
    }

    private void union(int u, int v) {
        int uID = find(u);
        int vID = find(v);
        if (uID != vID) {
            computers[uID] = vID;
        }
    }

}
